P1064 金明的预算方案
存在依赖关系背包转化分组背包。
题意
给定 个物品的价值和体积,他们之间存在简单的依赖关系,即一个结点要么是父亲结点,要么是儿子结点,且一个父亲结点最多有两个儿子结点。
Nothing with me, but Forever.
存在依赖关系背包转化分组背包。
给定 n 个物品的价值和体积,他们之间存在简单的依赖关系,即一个结点要么是父亲结点,要么是儿子结点,且一个父亲结点最多有两个儿子结点。
考虑现在有 n 本书并给定一个最大长度 L,第 i 本书有高度 hi,wi。每次选取一段范围满足该段范围内的所有书的 ∑wi≤L,那么这次选取的贡献为 max{hi}。
给定的数据范围是一个弱化版本。
给定 n 个点权 {a},并按照规则:对于 i,j,如果 i&j=0 则对 i,j 连边,生成图 G。
现在要求 G 中的每个点都要按照如下规则加入集合 S:
求最大贡献,n≤2×103,ai≤109。
给定一棵有 n 个结点的树,每次操作选取 3 个点 i,j,k 满足 i,j 存在连边,j,k 存在连边,定义一次操作为:
求最小的操作次数使得树存在度为 n−1 的点。
现在给定一个序列 {a},令 f(i,j)=j−iai×aj。对于每个 i,计算出所有满足 j≤i×k 的 f(i,j),(其中 k 为一个小于 0.35 的常量),相对误差小于 5%。
周末的赛题,然而考场上因为 E 题的一点细节没处理好,只剩下 30 min 来写 F,想到了做法后索性就没写 Code 了。